跳到主要内容

GMRES 算法

阐述​

用于求解线性方程 Ax=bAx=b。取 n≪mn\ll m，首先利用 Krylov 子空间法和 Gram-Schmidt 正交化构造出 nn 维正交基，然后找到一个在子空间内的最佳解，即

min⁡x∈Kn∥Ax−b∥2=min⁡y∈Cn∥AQny−b∥2=min⁡y∈Cn∥H^ny−e1∥b∥2∥\min_{x\in\mathcal K_n}\|Ax-b\|_2=\min_{y\in\mathbb C^n}\|AQ_ny-b\|_2=\min_{y\in\mathbb C^n}\|\hat H_ny-e_1\|b\|_2\|

预条件​

预条件是指把 Ax=bAx=b 转化为 MAx=MbMAx=Mb 来求解，其中 MAMA 具有某种更好的性质。MM 往往是以各种方式近似 A−1A^{-1}，或者先近似 A^\hat A 然后计算 A^−1\hat A^{-1}.

  • Jacobi：用对角元来近似 AA
  • 不完整的 LU 分解，然后用稀疏的 L 和 U 来近似 AA
  • 多格点

实例​

性质​

收敛性​

GMRES 等价于找到一个多项式 ρ(λ)\rho(\lambda) 在所有 λ\lambda 上尽可能小，因为

min⁡x∈Kn∥Ax−b∥2=min⁡ρ∈Pn,ρ(0)=1∥ρ(A)b∥2\min_{x\in\mathcal K_n}\|Ax-b\|_2=\min_{\rho\in P_n,\rho(0)=1}\|\rho(A)b\|_2

在 AA 可以对角化的情况下，上式化为：

∥rn∥2≤∥b∥K(V)min⁡ρ∈Pn(max⁡i∣ρ(λi)∣)\|r_n\|_2\le\|b\|\mathcal K(V)\min_{\rho\in P_n}\left(\max_i|\rho(\lambda_i)|\right)

因此如果 λ\lambda 比较集中，那么收敛就快。这个分析也表明，GMRES 不是平移不变的。

相关内容​

参考文献​